import java.util.Arrays;

/**
* @description: 1024. 视频拼接
* @author hewei
* @date 2022/10/5 15:36
* @version 1.0
*/

public class VideoStitching {

    public static void main(String[] args) {
        int[][] nums = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
        System.out.println(new VideoStitching().videoStitching(nums, 10));
    }

    public int videoStitching1(int[][] clips, int time) {
        int start = 0;
        int end = time;
        int ans = 0;
        while (start < end) {
            int temp1 = start;
            int temp2 = end;
            for (int[] clip : clips) {
                int l = clip[0];
                int r = clip[1];
                if (l <= start && r > temp1) temp1 = r;
                if (temp1 >= end) return ans + 1;
                if (r >= end && l < temp2) temp2 = l;
            }
            if (temp1 == start && temp2 == end) return -1;
            start = temp1;
            end = temp2;
            ans += 2;
        }
        return ans;
    }

    public int videoStitching(int[][] clips, int time) {
        int[] dp = new int[time + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for (int i = 1; i < time + 1; i++) {
            for (int[] clip : clips) {
                if (clip[0] < i && clip[1] >= i) {
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }
        return dp[time] == Integer.MAX_VALUE - 1 ? -1 : dp[time];
    }
}